package exercise02;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

// 长度最小的子数组
// 时间复杂度 O(n)
public class Day230707 {
    // 滑动窗口（同向双指针）
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int len = 0;
        int minLen = Integer.MAX_VALUE;
        // while 后面这判断， 主要是因为 right 越界后，sum 还是大于target，需要出窗口
        while (right < nums.length || sum >= target) {
            if (sum < target) {
                // 元素进窗口
                sum += nums[right];
                len++;
                right++;
            } else {
                // 元素出窗口
                // 更新结果
                minLen = Math.min(minLen, len);
                sum -= nums[left];
                len--;
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    // 代码更简洁, 优雅
    public int minSubArrayLen1(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        while (right < nums.length) {
            // 元素进窗口
            sum += nums[right++];
            // 进窗口一次，可能要出窗口好几次
            // 如果是最后一个元素进窗口，right = nums.length 了
            while (sum >= target){
                // 元素出窗口
                // 更新结果
                minLen = Math.min(minLen, right - left);
                sum -= nums[left++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

// 无重复字符的最长子串
// 时间复杂度 O(n)
class Solution2 {
    // 用 HashSet 来判断有无重复字符
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        int n = s.length();
        int len = 0;
        Set<Character> set = new HashSet<>();
        while (right < n) {
            char cur = s.charAt(right++);
            while (set.contains(cur)) {
                // 出现重复字符，将元素出窗口，left 跳过重复字符后，再继续操作
                // 元素出窗口
                set.remove(s.charAt(left++));
            }
            // 元素进窗口
            set.add(cur);
            // 更新最长子串长度
            len = Math.max(len, set.size());
        }
        return len;
    }

    // 用数组模拟哈希表，进行判断字符是否有重复
    public int lengthOfLongestSubstring2(String s) {
        int left = 0;
        int right = 0;
        int n = s.length();
        int len = 0;
        int[] hash = new int[128];
        while (right < n) {
            char cur = s.charAt(right++);
            while (hash[cur] == 1) {
                // 出现重复字符，将元素出窗口，left 跳过重复字符后，再继续操作
                // 元素出窗口
                hash[s.charAt(left++)]--;
            }
            // 元素进窗口
            hash[cur]++;
            // 更新最长子串长度
            len = Math.max(len, right - left);
        }
        return len;
    }
}
